- Title
- Solution sets for equations over free groups are EDT0L languages
- Creator
- Ciobanu, Laura; Diekert, Volker; Elder, Murray
- Relation
- 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015). Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015 Kyoto, Japan, July 6-10, 2015 Proceedings, Part II (Kyoto, Japan 6-10 July, 2015) p. 134-145
- Relation
- ARC.FT110100178
- Publisher Link
- http://dx.doi.org/10.1007/978-3-662-47666-6_11
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2015
- Description
- We show that, given a word equation over a finitely generated free group, the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. The question of whether a description of solution sets in reduced words as an indexed language is possible has been open for some years, apparently without much hope that a positive answer could hold. Nevertheless, our answer goes far beyond: they are EDT0L, which is a proper subclass of indexed languages. We can additionally handle the existential theory of equations with rational constraints in free products 1≤i≤sFi, where each Fi is either a free or finite group, or a free monoid with involution. In all cases the result is the same: the set of all solutions in reduced words is EDT0L. This was known only for quadratic word equations by, which is a very restricted case. Our general result became possible due to the recent recompression technique of Jeż. In this paper we use a new method to integrate solutions of linear Diophantine equations into the process and obtain more general results than in the related paper. For example, we improve the complexity from quadratic nondeterministic space in to quasi-linear nondeterministic space here. This implies an improved complexity for deciding the existential theory of non-abelian free groups: NSPACE(n log n). The conjectured complexity is NP, however, we believe that our results are optimal with respect to space complexity, independent of the conjectured NP.
- Subject
- algorithm analysis; problem complexity; computation by abstract devices; computer communication networks; information storage and retrieval; information systems applications; discrete mathematics
- Identifier
- http://hdl.handle.net/1959.13/1307688
- Identifier
- uon:21496
- Identifier
- ISBN:9783662476659
- Rights
- The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-47666-6_11
- Full Text
- Reviewed
- Hits: 1441
- Visitors: 1621
- Downloads: 232
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 481 KB | Adobe Acrobat PDF | View Details Download |